package com.xq.algorithm.sort;

import static com.xq.algorithm.AlgorithmTest.printlnAry;

/**
 * @author jltxseo
 *         Created by junlintianxia on 2017/07/09.
 *         交换排序：1.冒泡排序 2.快速排序
 */

public class SwapSortAlgorithm {

    /**
     * 冒泡排序
     * 冒泡排序通过重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来，
     * 直到没有再需要交换的元素为止（对n个项目需要O(n^2)的比较次数）。
     * 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
     * @param a
     * 最差时间复杂度O(n^2)
     * 最优时间复杂度 O(n)
     * 平均时间复杂度 O(n^2)
     * 最差空间复杂度总共O(n)，需要辅助空间O(1)
     */
    public static void  bubbleSort(int[] a){
        if( a == null)return;
        int n = a.length;
        for(int i=0; i < n-1; i++){
            for(int j= i+1; j < n;j++){
                if(a[i] > a[j]){
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
            }
            printlnAry(a);
        }
    }

    public static void testBubbleSort(){
        int[] a = {95,45,15,78,84,51,24,12};
        printlnAry(a);
        bubbleSort(a);
        printlnAry(a);
    }

    /**
     * 快速排序（Quicksort）是对冒泡排序的一种改进，又称划分交换排序
     * 快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
     * 步骤为：
     * ①．从数列中挑出一个元素，称为"基准"（pivot）
     * ②．重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
     * 在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
     * ③．递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
     *
     * 在平均状况下，排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。
     * 事实上，快速排序通常明显比其他Ο(n log n)算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
     * 最差时间复杂度	Ο(n^2)　
     * 最优时间复杂度	Ο(n log n)　
     * 平均时间复杂度Ο(n log n)
     * @param a
     * @param low
     * @param hight
     */
    public static void quickSort(int[] a,int low,int hight){
        int i = low, j = hight;
        int temp = a[low];
        while (i < j){
            while (i < j && temp <= a[j]){ //从右边开始扫描
                j--;
            }
            if(i < j){  //将小于基准值得数交换
                a[i] = a[j];
                i++;
            }

            while (i < j && temp > a[i]){  //从左边开始扫描
                i++;
            }

            if(i < j){  //将大于基准值得数交换
                a[j] = a[i];
                j--;
            }
        }
        a[i] = temp;

        if(low < i) quickSort(a,low,i-1);
        if(i < hight)quickSort(a,j+1,hight);
    }


    public static void testQuickSort(){
        int[] a = {95,45,15,78,84,51,24,12};
        printlnAry(a);
        quickSort(a,0,a.length -1);
        printlnAry(a);
    }
}
